Modularidad y Topologías Virtuales (página 2)

Partes: 1, 2, 3

Modularidad.

Modularidad. Ejemplo
El siguiente ejemplo toma como punto de partida los dos comunicadores creados en el ejemplo anterior: uno con los procesos que en MPI_COMM_WORLD tienen dirección par, y otro con los que tienen en ese comunicador dirección impar. Cada proceso tiene almacenado en newcom el comunicador al que pertenece, y en myotherid su dirección en ese comunicador. Tras crear, de forma colectiva, el intercomunicador, cada proceso del comunicador “par” envía un mensaje a su semejante en el comunicador “impar”.

Modularidad. Ejemplo
if (myglobalid%2 == 0) {
MPI_Intercomm_create (newcom, 0, MPI_COMM_WORLD,
1, 99, &intercomm);
MPI_Send(msg, 1, type, myotherid, 0, intercomm);
}
else {
MPI_Intercomm_create (newcom, 0, MPI_COMM_WORLD,
0, 99, &intercomm);
MPI_Recv(msg, 1, type, myotherid, 0, intercomm, &status);
}

Topologías virtuales
Particionar: debemos definir como asignar partes (el rango [s,e))a cada proceso.

La forma en que el hardware está conectado entre sí se llama “topología de la red” (anillo, estrella, toroidal …)

La forma óptima de particionar y asignar a los diferentes procesos puede depender del hardware subyacente. Si la topología del hardware es tipo anillo, entonces conviene asignar franjas consecutivas en el orden en que avanza el anillo.

En muchos programas cada proceso comunica con un número reducido de procesos vecinos. Esta es la “topología de la aplicación”.

Topologías virtuales
Para que la implementación paralela sea eficiente debemos hacer que la topología de la aplicación se adapte a la topología del hardware.

MPI permite al vendedor de hardware desarrollar rutinas de topología especializadas a través de la implementacióon de las funciones de MPI de topología.

Al elegir una “topología de la aplicación” o “topología virtual”, el usuario está diciendo como va a ser preponderantemente la comunicación. Sin embargo, como siempre, todos los procesos podrán comunicarse entre sí.

Topologías virtuales
La topología virtual más simple (y usada corrientemente en aplicaciones numéricas) es la “cartesiana”.

En la forma en que lo describimos hasta ahora, usaríamos una topología cartesiana 1D, pero en realidad el problema llama a una topología 2D. También hay topologías cartesianas 3D, y de dimensión arbitraria

Topologías virtuales
En la topología cartesiana 2D a cada proceso se le asigna una tupla de dos números (I; J). MPI provee una serie de funciones para definir, examinar y manipular estas topologías.

La rutina MPI_Cart_create(…) permite definir una topología cartesiana 2D.

MPI-Cart-create(MPI-Comm comm-old, int ndims,2 int *dims,
int *periods, int reorder, MPI-Comm *new-comm);

dims: vector que contiene el número de filas/columnas en cada dirección.
periods: un vector de flags que indica si una dirección dada es periódica o no.
reorder: El argumento bool reorder activado quiere decir que MPI puede reordenar los procesos de tal forma que optimice la relación entre la topología virtual y la de hardware.

Topologías virtuales
Ejemplo:

…
int dims[2]={4,4}, periods[2]={0,0};
MPI-Comm comm2d;
MPI-Cart-create(MPI-COMM-WORLD,2,dims, periods, 1, comm2d);
…

Topologías virtuales
Ejemplos de topologías virtuales:

Topologías virtuales
MPI_Cart_get() permite recuperar las dimensiones, periodicidad y coordenadas (dentro de la topología) del proceso.

int MPI-Cart-get(MPI-Comm comm, int maxdims, int *dims,
int *periods, int *coords );

Con MPI_Cart_coords() se pueden conseguir directamente sólo la tupla de coordenadas del proceso en la topología.

int MPI_Cart_coords(MPI-Comm comm,int rank, int maxdims,
int *coords);

Topologías virtuales
Antes de hacer una operación de actualización uk ? uk+1 , tenemos que actualizar los ghost values.
Por ejemplo, con una topología 1D:
Enviar e-1 a P+1
Recivir e de P+1
Enviar s a P-1
Recivir s-1 de P-1

Topologías virtuales
En general se puede ver como que estamos haciendo un “shift” de los datos hacia arriba y hacia abajo.

Esta es una operación muy común y MPI provee una rutina (MPI_Cart_shift()) que calcula los rangos de los procesos para una dada operación de shift:

int MPI-Cart-shift(MPI-Comm comm,int direction,int displ,
int *source,int *dest);

Por ejemplo, en una topolog´ia 2D, para hacer un shift en la dirección horizontal

int source-rank, dest-rank;
MPI-Cart-shift(comm2d,0,1,
&source-rank,&dest-rank);

Topologías virtuales
Que ocurre en los bordes? Si la topología es de 5×5, entonces un shift en la direccion 0 (eje x) con desplazamiento displ = 1 para el proceso (4; 2) da

Topologías virtuales
MPI_PROC_NULL es un “proceso nulo”. La idea es que enviar a MPI_PROC_NULL equivale a no hacer nada (como el /dev/null de Unix).

Una operación como

MPI-Send(. . .,dest,. . .)

equivaldría a

if (dest != MPI-PROC-NULL)
MPI-Send(. . .,dest,. . .);

Topologías virtuales
Si el número de filas a procesar n-1 es múltiplo de size, entonces podemos calcular el rango [s,e) de las filas que se calculan en este proceso haciendo

s = 1 + myrank*(n-1)/size;
e = s + (n-1)/size;

Si no es múltiplo podemos hacer:

// All receive ‘nrp’ or ’nrp+1’
// First ‘rest’ processors are assigned ’nrp+1’
nrp = (n-1)/size;
rest = (n-1) % size;
s = 1 + myrank*nrp+(myrank &weights,vector &nrows) {
int size = weights.size();
nrows.resize(size);
double sum-w = 0., carry=0., a;
for (int p=0; p< tol);
}

Topologías virtuales. Ejemplo
La siguiente función reparte n objetos entre size procesadores con pesos weights[].

void decomp(int n,vector &weights,vector &nrows) {
int size = weights.size();
nrows.resize(size);
double sum-w = 0., carry=0., a;
for (int p=0; p< tol);
}

Esto es hacer “balanceo estático” de carga

Ejemplos
#include

/* Run with 12 processes */

void main(intargc, char *argv[]) {
int rank;
MPI_Comm vu;
int dim[2],period[2],reorder;
int coord[2],id;

MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD,&rank);

dim[0]=4; dim[1]=3;
period[0]=TRUE; period[1]=FALSE;
reorder=TRUE;